
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-03-29
 * Time: 17:39
 */
public class BTree {
    static class BTNode{
        public int[] keys;  // 关键字
        public BTNode[] subs; // 孩子
        public BTNode parent;
        // 用来记录这个节点中 keys 数组中有多少数据, 以便判断是否需要分裂
        public int usedSize;
        public BTNode(){
//            为了方便分裂, keys 和 subs　都多开辟一块空间
//            多开辟一块空间, 就可以先把数据填上去, 就很容易判断哪个是中间节点
            this.keys=new int[M];
            this.subs=new BTNode[M+1];
        }
    }

    public static final int M=3; // 每个节点中最多存储的 孩子的数量
    public BTNode root;  // 当前 B 树的根节点


    /**
     * 往 B 树里面插入一个元素
     * @param key
     * @return
     */
    public boolean insert(int key){
//      1. B 树为空,  第一次插入节点
        if(root==null){
            root=new BTNode();
            root.keys[0]=key;
            root.usedSize++;
            return true;
        }
//      2. B 树不为空, 不是第一次插入节点, 就需要找到合适位置
//        所以不用管 subs
        Pair<BTNode , Integer> position=find(key);   // 找到应该插入的位置
        if(position.getV()!=-1){
//            如果已经有相同的节点
            return false;
        }
//      3. 不存在值相同 的节点
        BTNode parent=position.getK();
//        将数据插入: 使用插入排序
//        先找到正确的位置
        int index=parent.usedSize-1;
        while(index>=0&&parent.keys[index]>=key){
            parent.keys[index+1]=parent.keys[index];
            index--;
        }
//        插入数据
        parent.keys[index+1]=key;
//        不要忘记 usedSize ++
        parent.usedSize++;
//        注意: 这里的插入 全部都是插入到叶子节点, 所以不用处理孩子节点
//        判断是否需要分裂
        if(parent.usedSize== M){
//            满了需要分裂
            split(parent);
        }
        return true;
    }

    private void split(BTNode cur) {
        int mid=cur.usedSize>>1; // 中间节点的位置
        int i=mid+1;  // 旧节点的 keys 的右半部分的起始下标
        int j=0;   // 新节点的 keys 的起始下标
        BTNode newNode=new BTNode(); // 分裂出来的右边的新节点
//        右半部分 分离出来
        for(;i<cur.usedSize;i++){
            newNode.keys[j]=cur.keys[i];
            newNode.subs[j]=cur.subs[i];
            // 不要忘记处理 孩子节点, 因为他们的父亲节点已经变了
            if(newNode.subs[j]!=null){
                newNode.subs[j].parent=newNode;
            }
            j++;  // 不要忘记 j++
        }
        // 多拷贝一次 最右边的子节点
        newNode.subs[j]=cur.subs[i];
        if(newNode.subs[j]!=null){
            newNode.subs[j].parent=newNode;
        }
        // 更新当前节点的有效数据个数
        newNode.usedSize=j;
        cur.usedSize=cur.usedSize-j-1; // 1 代表需要提到父亲节点上面的中间节点
//        中间节点提上去
        BTNode parent=cur.parent;
//        先判断是不是根节点, 如果是根节点, 树的高度需要增加
        if(parent==null){
            parent=new BTNode();
            parent.keys[0]=cur.keys[mid];
            parent.subs[0]=cur;
            cur.parent=parent;
            parent.subs[1]=newNode;
            newNode.parent=parent;
            parent.usedSize++;
//         更新一下根节点
            root=parent;
            return ;
        }
//            parent 不为空, 即不是根节点
        int k=parent.usedSize-1;
        int midValue=cur.keys[mid];
        while(k>=0&&parent.keys[k]>=midValue){
            parent.keys[k+1]=parent.keys[k];
//            不要忘记处理孩子
            parent.subs[k+2]=parent.subs[k+1];
            k--;
            // parent.subs[k] 就不用管, 因为它就是 cur 这个节点
        }
//            中间节点提上去,挪动数据,  并连接新的左右节点
        parent.keys[k+1]=midValue;
        parent.usedSize++;
        parent.subs[k+1]=cur;
        parent.subs[k+2]=newNode;
//        更新当前节点的父亲节点
        newNode.parent=parent;
//        如果 parent 节点也需要分裂了, 那么递归
        if(parent.usedSize>= M){
            split(parent);
        }
    }

    /**
     * 查找要插入的位置
     * @param key 因为如果出现相同的值, 那么需要将 这个节点的位置返回, 所以用到了 Pair
     * @return
     */
    private Pair<BTNode, Integer> find(int key) {
        BTNode cur=root;
        BTNode parent=null;
        while(cur!=null){
            parent=cur;
            int i=0;
            for(;i<cur.usedSize;i++){
                if(cur.keys[i]>key){
                    break;
                } else if(cur.keys[i]==key){
                    return new Pair<>(cur, i);
                }
            }
            cur=cur.subs[i];
        }
        return new Pair<>(parent, -1);
    }


    /**
     * B树的中序遍历, 结果有序
     * @param root
     */
    public void inorder(BTNode root){
        if(root==null){
            return ;
        }
        for (int i = 0; i < root.usedSize; i++) {
            inorder(root.subs[i]);
            System.out.print(root.keys[i]+" ");
        }
        inorder(root.subs[root.usedSize]);

    }
}
